
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage[breaklinks]{hyperref}
\usepackage{array}
%\usepackage{url}
%\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
%\urldef{\mailsb}\path|anna.kramer, leonie.kunz, christine.reiss, nicole.sator,|
%\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}@springer.com|    
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}
\clubpenalty = 10000
\widowpenalty = 10000
\displaywidowpenalty = 10000
					
\usepackage[T1]{fontenc}
\usepackage{ae,aecompl}
\input{commands.tex}
\input{commands1.tex}
\usepackage{epsfig}
\linespread{0.95}
\newtheorem{name}{Printed output}
\newcommand{\choreos}[0]{\textit{CHOReOS}~}
\usepackage{listings}


\lstset{language=Python,
        morekeywords=[1]{yield}
}  

% pre-load the language
\lstloadlanguages{Python} %  comma separated list of languages


% Style
% ~~~~~
% 
% Typeface settings::

\lstset{
  basicstyle=\tt\scriptsize,           % print whole listing in tt
  % basicstyle=\ttfamily\small,   % and, maybe small    
  keywordstyle=\bf,
  % identifierstyle=\slshape,     % object names
  commentstyle=\itshape, % italic comments
  stringstyle=\slshape,           % strings
}

\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{QoS Analysis in Heterogeneous Choreography Interactions}

% a short form should be given in case it is too long for the running head
\titlerunning{QoS Analysis in Heterogeneous Choreography Interactions}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Ajay Kattepur, Nikolaos Georgantas \& Val\'erie Issarny%
%\thanks{Please note that the LNCS Editorial assumes that all authors have used
%the western naming convention, with given names preceding surnames. This determines
%the structure of the names in the running heads and the author index.}%
}
%
\authorrunning{QoS Analysis in Heterogeneous Choreography Interactions}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{Equipe ARLES, INRIA Paris-Rocquencourt, France.\\
$email$: firstname.lastname@inria.fr}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle


\begin{abstract}
With an increasing number of services and devices interacting in a decentralized manner, \emph{choreographies} are an active
area of investigation. The heterogeneous nature of interacting devices leads to choreographies
that may not only include services, but also sensor-actuator networks, databases and service feeds. Their middleware behavior within choreographies
is captured through abstract interaction paradigms such as \emph{client-server}, \emph{publish-subscribe} and \emph{tuple spaces}.  In this paper, we study these interaction paradigms that are connected through an extensible service bus abstracted by the \emph{generic application} middleware connector proposed in the \choreos project, that enables heterogeneous device interoperability. As the functioning of such choreographies is dependent on the Quality of Service (QoS) performance of participating entities, an intricate analysis of interaction paradigms and their effect on QoS metrics is needed. We study the composition of QoS metrics in heterogeneous choreographies through such interactions, connectors and the subsequent tradeoffs. This produces interesting insights such as selection of a particular implementation during design time or end-to-end QoS expectation/guarantees during runtime. A non-parametric Kolmogorov-Smirnov hypothesis test is also provided where certain QoS dependent interaction connectors may be replaced to prevent deterioration in performance.
\keywords{Heterogeneous Choreographies, Quality of Service, Interaction Paradigms, Middleware Connectors.}
\end{abstract}


\section{Introduction}

Unlike orchestrations that have a centralized control flow, choreographies involve a shared service composition framework where only the participants' functionality and associated message passing are described \cite{orch_chor},\cite{barker}. Service Oriented Architectures (SOA) allow components to interact via standard interfaces, with the enterprise service bus (ESB) \cite{esb} providing a middleware-level bus protocol to convey such interactions. These are based mainly on client-server interaction paradigms, as for instance, with REST \cite{restful} based web services.

While conventional service choreographies accommodate stateless or stateful services, heterogeneous choreographies that involve sensor networks and data feeds, such as those seen in the \emph{Internet of Things} \cite{iot1}, require additional interaction paradigms \cite{Glombitza}. Heterogeneous devices are handled in the middleware level with varied interactions, data structures and communication protocols made interoperable. The middleware platforms such as REST \cite{restful} based client-server interactions, Java Messaging Service \cite{JMS} based publish-subscribe or JavaSpaces \cite{javaspaces} for Tuple Spaces are made interoperable through this. 

In this paper, we use an extensible service bus (XSB) proposed in the \choreos project \url{http://www.choreos.eu/bin/view/Main/} \cite{choreos} in order to deal with the heterogeneous aspects of choreographies. The common protocol is provided by the abstract \emph{Generic Application} (GA) connector, which preserves the interaction paradigms of the individual components while still allowing interoperability. We examine the effect of various message interaction protocols: \emph{Client-Server}, \emph{Publish-Subscribe} and \emph{Tuple Spaces}.

Studies that characterize the Quality of Service (QoS) in web services have received attention with regards to discovery, late-binding and optimal end-to-end compositions \cite{QoS_composition}. QoS analysis has conventionally been done at the application level; heterogeneous choreographies consisting of services and sensor networks would require further analysis of paradigms or have QoS aware middleware \cite{qos_middleware}. An intricate analysis of QoS at the abstract level of interaction paradigms, rather than application level, would provide guidelines on how to deal with QoS-aware Heterogeneous choreographies.

In this work, middleware paradigms that support heterogeneous choreographies are enhanced with QoS composition frameworks. Consolidating the research done in QoS composition along with middleware paradigms provides an interesting outlook. By fine grained analysis of interactions, we evaluate the performance of choreography participants in relation to heterogeneous paradigms. This methodology can have beneficial effects: 1) Design time selection of interaction paradigms to match required functional and QoS goals 2) Runtime analysis of composed choreographies to prevent deterioration of end-to-end QoS of participants. Such an analysis leads to interesting outlooks including the use of Kolmogorov-Smirnov hypothesis testing to replace an interaction paradigm with another when abstracted with a particular QoS metric.

The rest of the paper is organized as follows: Section \ref{sdjkfsdjknbjk} provides and overview of heterogeneous interaction paradigms and the generic application connectors proposed in the \choreos project. The QoS domains, metrics and algebra for composition are studied in Section \ref{wdklghskdjlhfialhlk}. The methodology of propagating QoS increments and their subsequent composition are analyzed in Section \ref{kldakljasdfjk}. The results of our analysis through experiments are presented in Section \ref{sdkgjlksdjgklsjglsjd}, which includes an analysis of tradeoffs and interaction substitution. This is followed by related work and conclusions in Sections \ref{fsdmlkjflksdjk} and \ref{dfjsudhfiuwshhio}, respectively. 

\section{Heterogeneous Interaction Paradigms}
\label{sdjkfsdjknbjk}
\noindent In this section, we briefly describe the three message interaction paradigms that may be abstractly applied within our framework \cite{mom}. This is followed by an overview of the generic application connectors that ensure interoperability among these interactions. 

\subsection{Interaction Paradigms}
In order to let choreographies include services (typically client server interactions), service broadcasts (publish-subscribe) and asynchronous sensor-actuator database sharing (tuple space), it is a requirement to allow maximum heterogeneity. We briefly review the relevant interaction paradigms in Table \ref{Pdeskjfhksjgdjhg} and discuss their interfaces \cite{nikolaos}.

	\begin{table}[ht]
		\vspace{-0.2in}
		\centering
	\begin{tabular}{|p{2.8cm} |p{3.1cm} | p{6.5cm}|}
	\hline
	\textbf{Interaction} & \textbf{Primitives}&\textbf{Arguments}\\ \hline
  Client-Server & 
	\texttt{request} & \texttt{destination, operation, input}\\
	&\texttt{sync\_response} & $\uparrow$\texttt{source,} \texttt{operation,} $\uparrow$\texttt{output, timeout}\\
	&\texttt{async\_response} & $\uparrow$\texttt{source,} \texttt{operation,} $\uparrow$\texttt{output, callback}\\
	&\texttt{notify} & \texttt{callback, source, output}\\
	&\texttt{async\_end\_response} & \texttt{callback}\\ \hline
	
	Publish-Subscribe &	\texttt{publish} & \texttt{broker, filter, event, lease}\\
	&\texttt{subscribe} & \texttt{broker, filter, $\uparrow$handle}\\
	&\texttt{get\_next} & \texttt{handle, $\uparrow$event, timeout}\\
	&\texttt{listen} & \texttt{handle, callback}\\
  &\texttt{notify} & \texttt{callback, event}\\
	&\texttt{end\_listen} & \texttt{callback}\\
	&\texttt{unsubscribe} & \texttt{handle}\\ \hline
	
	Tuple Space & \texttt{write} & \texttt{tuple\_space, template, tuple, lease} \\
	&\texttt{take} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, timeout}\\
	&\texttt{read} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, timeout}\\
	&\texttt{register} & \texttt{tuple\_space, template, callback}\\
	&\texttt{notify} & \texttt{callback}\\
  &\texttt{unregister} & \texttt{callback}\\ \hline
	\end{tabular}
	\caption{APIs of Interaction Paradigms.}
	\label{Pdeskjfhksjgdjhg}
	\vspace{-0.5in}
	\end{table}
	
\begin{itemize}
	\item \emph{Client-Server} (CS) - Commonly used interaction paradigm for web services. The client may send a \emph{request} and block further execution
	until synchronization with a received \emph{response}. A \emph{callback} can also be asynchronously received by the middleware which then sets up a notification to the client. The API is shown with $\uparrow$ representing the return argument of a primitive. It represents tight \emph{space} (knowledge of senders, receivers) and \emph{time} (client-server availability) coupling.
		\item \emph{Publish-Subscribe} (PS) - Commonly used interaction paradigm for content broadcasting/feeds. In this, multiple \emph{peers} interact with the \emph{publisher} with an intermediate \emph{broker} service. Publishers produce events that may be forwarded to peers via the broker until a \emph{lease} period. Additional filtering of messages may be done with respect to \emph{subscriptions} of the peers. This interaction paradigm allows \emph{space} decoupling as the peers need not know each other. Additionally, \emph{time} decoupling is possible with the disconnected clients receiving updates synchronously / asynchronously(callback) when reconnected to the broker. 
	\item \emph{Tuple Space} (TS) - Commonly used for shared data with multiple read/write users. In this, multiple \emph{peers} interact with a \emph{shared space}, with peers having write, read and data removal (take) access. The peers can retrieve data that pattern matches a \emph{tuple} value either synchronously or through notifications. This interaction enables both space and time decoupling between interacting peers.

\end{itemize}
	
%These interaction paradigms are represented in Fig. \ref{dfl;jglksjdfls}.
%
%\begin{figure}[ht]
%\centering
%\includegraphics[height=14cm]{interaction.eps}
%\caption{Message Interaction Paradigms}
%\label{dfl;jglksjdfls}
%\end{figure}

\subsection{Generic Application (GA) Connectors}

The \choreos \cite{choreos} project uses the following abstractions to deal with large scale choreographies that connect heterogeneous, adaptable and QoS-aware participants:
\begin{itemize}
	\item \emph{Components}: The heterogeneity of the services and devices encountered are modeled as service abstractions, which
represent groups of alternative services/things that provide similar functional/non-functional properties
through different interfaces. 
\item \emph{Connectors}: The \choreos connector
definition relates to the introduction of a new multi-paradigm connector type, called the \emph{GA connector},
which allows component services to interoperate even if they are based on heterogeneous
paradigms. It uses an extensible service bus (XSB) protocol that extends the conventional ESB to interoperate additional interaction paradigms. 
\item \emph{Coordination Delegates}: These are used to enforce the realizability of choreographies
despite the autonomy of the composed services. They ensure that the choreography specifications are adhered to by the
participating entities.
\end{itemize}
The generic representation of the \choreos model is shown in Fig. \ref{fig:CHOReOS} with \emph{services/devices} represented by \emph{components} to abstract behavior. The functional interface of the choreography participants provides a description of the \emph{operations}, \emph{messages} and \emph{constraints}. Note that there are multiple devices that may participate:
\begin{enumerate}
	\item \emph{Stateless Services}: These are just treated atomically with client-server requests-responses.
	\item \emph{Composite/Stateful Services}: Modeled as orchestrations that can have varied internal control flow. Note that the interface may hide the internal behavior and these may be considered a distributed implementation of a single \emph{stateful} service.
	\item \emph{Data Feed Services}: Typically publish data periodically that is then passed to subscribers of the feed.
	\item \emph{Sensor Actuator Networks}: The networks coordinate through a tuple space-like interaction.
\end{enumerate}
At the choreography level in Fig. \ref{fig:CHOReOS}, the \emph{coordination delegates} can wrap such services and adapt their roles to choreography message passing specifications. The \emph{generic application (GA) connectors} ensure interoperability across a host of middleware protocols (client-server, publish-subscribe, tuple spaces). 

\begin{figure}
\vspace{-0.1in}
	\centering
		\includegraphics[width=8cm]{choreos_GA.eps}
	\caption{\choreos Choreography Model \cite{choreos}.}
	\label{fig:CHOReOS}
\end{figure}

The GA connector has been proposed that behaves as an extension to the conventional SOA ESB, allowing for varied messaging protocols to interact. The GA connectors employ primitives such as \texttt{get} and \texttt{post} to abstract CS (\texttt{request, response}), PS (\texttt{getnext, publish}) and TS (\texttt{read, write}) interactions. Further, multiple space-time coupling schemes are incorporated: strong (CS), weak (PS), very weak (TS). The following table abstracts the API for the GA connector with \emph{scope} allowing for single-client (CS) or filtering data types (TS, PS). In \cite{choreos}, the GA connector are shown to have similar behavioral semantics and interaction states when mapped to CS/TS/PS interactions. 
	
%An example of the interaction patterns possible through the GA connectors are shown in Fig. \ref{dsddsgdsxfs}. Notice that a composite service participating in the choreography through a \emph{request-response} paradigm can connect to a generic application connector. The binding component converts the \emph{post/get} interaction to those specified by TS/PS interactions. This allows streaming protocol data and sensor network data to be exposed as client-server interactions to composite services. 
	

		\begin{table}[ht]
	\centering
	\begin{tabular}{|p{3cm} | p{9cm}|}
	\hline
	\textbf{Primitives}&\textbf{Arguments}\\\hline
	\texttt{post} & \texttt{coupling\{strong, weak, very weak\}, scope\{(source-destination | broker | tuplespace), (operation | filter | template)\}, data, lease}\\
	\texttt{set\_get}& \texttt{coupling, $\uparrow$scope, $\uparrow$handle}\\
	\texttt{get\_sync}& \texttt{handle, policy, $\uparrow$data, timeout}\\
	\texttt{get\_async}& \texttt{handle, $\uparrow$data, callback}\\
	\texttt{notify} & \texttt{callback, scope, data}\\
	\texttt{end\_get\_async}&\texttt{callback}\\
	\texttt{end\_set\_get}&\texttt{handle} \\\hline
	\end{tabular}
	\caption{Generic Application Connector API.}
				\vspace{-0.3in}
	\end{table}

While conventional middleware only study aspects of heterogeneity and functional interoperability, choreographies consider additional non-functional aspects
during design/runtime. This would specifically involve studying QoS performance of indivdual participants and their side-effects on choreography enaction. QoS metrics being probabilistic and multi-dimensional, accurate analysis of incements and composition rules are crucial, as discussed in the next section. 



\section{Quality of Service}
\label{wdklghskdjlhfialhlk}
\noindent In this section, the QoS domains that are of interest and the corresponding algebra for their composition are analyzed. 

\subsection{QoS Domains}
We review the basic domains of QoS that requires analysis for such interactions. We identify three basic domains \cite{pubsub_QoS}:

\begin{itemize}
\item $\delta$:~\emph{Timeliness} incorporates aspects such as latency and reliable message delivery. For the case of client server interactions, timeliness would mean studying the latency between synchronous request-response messages or time between notification and asynchronous message delivery. In case of publish-subscribe, the time of subscription and time of lease to ensure accurate delivery to peers needs to be studied. With tuple space, the possible concurrent read/write states must be analyzed for accurate delivery.
\item $\mathcal{S}$:~\emph{Security/Data Integrity} incorporates the trustworthiness of the interaction paradigms with respect to confidentiality of information. Specially in publish-subscribe subscription systems or tuple spaces where multiple peers have access to data. Malicious peers on the network must also be considered.
\item $\lambda$:~\emph{Resource Efficiency} incorporates multiple aspects such as efficiency in bandwidth usage and message passing.  Generally, this may be traded off with timeliness; greater bandwidth usage/active sessions might help in timely delivery of messages. Analysis of these tradeoffs will help understand the benefits of a particular interaction scheme.
\end{itemize}

\subsection{QoS Algebra}

In order to aggregate metrics available from such interactions, we make use of an algebraic framework as introduced in \cite{sidney6}. This can handle random variables drawn from  a distribution associated with a lattice domain. A \emph{QoS metric} $q$ is a tuple:
\beq
{q=(\Dom,\leq,\oplus, \bigwedge, \bigvee)}
\label {w0579wth0579}
\eeq
\begin{enumerate}
	\item $(\Dom,\leq)$ is a QoS domain with corresponding partially ordered set of QoS values 
	\item $\oplus: \mathbb{D} \times \mathbb{D} \rightarrow \mathbb{D}$ defines how QoS gets incremented by each new event. It satisfies the following conditions:
	\begin{itemize}
	\item $\oplus$ possesses a \emph{neutral element} $0$ satisfying $\forall q \in \mathbb{D} \Rightarrow q \oplus 0 = 0 \oplus q = q$.
	\item $\oplus$ is monotonic: $q_1 \leq q'_1$ and $q_2 \leq q'_2$ imply $(q_1 \oplus q_2) \leq (q'_1 \oplus q'_2)$.
%	\item Order $\qosleq$ is ``rich enough'': $\forall q,q' \in \mathbb{D}, ~\exists \delta q \in \mathbb{D} ~~\text{such that}~~ q \qosleq q' \qosoplus \delta q$. 
	\end{itemize}
	 \item $(\bigwedge, \bigvee)$ represent the lower and upper lattice, meaning that any $q \subseteq \Dom$ has a unique least lower, upper bound $(\bigwedge_{q}, \bigvee_{q})$. When taking the \emph{best} response with respect to the ordering $\leq$, the lowest QoS is taken with $\bigwedge$.
	When synchronizing events belonging the the causal past of a same event, the operator $\bigvee$ amounts to taking the worst QoS as per the ordering $\leq$.
%	\item $\qoscompet: \mathbb{D} \times {\mathbb{D}}^{*} \rightarrow \mathbb{D}$ is the competition operator that may be applied as choosing the ``best'' choice in many ways: pareto optimal, lexicographic or weighted choice. 	
	\end{enumerate}
%In addition, we make use of the native pruning operator in \orc\ to discard unused QoS tokens according to the semantics of \prunen. 
%
\begin{table}
\vspace{-0.2in}
\begin{center}
\begin{tabular}{|>{\centering}p{4cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering\arraybackslash}p{1.5cm}|} \hline
QoS Metric & $\Dom$ & $\leq$ & $\oplus$ & $\bigwedge$ & $\bigvee$ \\ \hline
$\delta$:~Timeliness & $\mathbb{R}_{+}$ & $<$ & $+$ & $\min$ & $\max$ ~~\\
$\mathcal{S}$:~Security/Data Integrity & $\mathbf{Q}$ & $>$ & $\bigvee$ & $\max$ &$\min$ ~~\\
$\lambda$:~Resource Efficiency & $\mathbf{Q}$  & $<$ & $+$ &$\min$ & $\max$ ~~\\ \hline
\end{tabular}
\end{center}
\caption[i76rtfi7]{Basic classes of QoS domains}
\label {0958th59pu}
\vspace{-0.3in}
\end{table}
%
Basic classes of QoS domains are displayed in Table~\ref{0958th59pu} and composed according to the specified rules. The use of this algebraic framework allows us to reason, in an abstract way, about the behavior of interaction protocols and their effect on choreography behavior. Such a specification may be invoked by any choreography description language to incorporate QoS composition. It specifies calculating the QoS increments with associated algebra with domains $\mathbb{D}$, partial order $\leq$ and operations $(\oplus, \bigvee, \bigwedge)$. In case of orchestrations, the increments and composition may be managed by the orchestrator itself (for monitoring SLAs, for instance). In case of choreographies, this has to be done in a distributed manner with every functional operation being tagged with a QoS increment. 

%An example specification in \emph{python} is shown below: 
%\begin{lstlisting}
%class Timeliness:                         # Timeliness
    %def __init__(self):
        %self.QoS = random.student_t(nu)   # student-t random variable
    %def QoSOplus(self,q2):                # oplus operator 
        %return (self.QoS + q2) 
    %def QoSCompare(self,q2):              # partial order
        %return self.QoS <= q2
    %def QoSInfimum(self,q2):              # infimum operator
        %v = [self.QoS,q2]
        %return v.sort()
    %def QoSSupremum(self,q2):             # supremum operator
        %return max(self.QoS,q2) 
				%
%class Security:                           # Security
    %def __init__(self):            
        %self.QoS = random.uniform(a,b)    # uniform random variable
    %def QoSOplus(self,q2):                # oplus operator
        %return min(self.QoS,q2) 
    %def QoSCompare(self,q2):              # partial order
        %return self.QoS >= q2
    %def QoSInfimum(self,q2):              # infimum operator
        %v = [self.QoS,q2]
        %return v.sort()    
    %def QoSSupremum(self,q2):             # supremum operator
        %return min(self.QoS,q2)    
%\end{lstlisting}

\section{QoS Analysis of Interactions}
\label{kldakljasdfjk}
In order to upgrade choreography interactions with QoS, we equip every operation $\mathcal{O}$ in a client-server, publish-subscribe or tuple space interaction with a QoS increment. This produces a tuple of $(\mathcal{O},\mathcal{Q})$ that may be propagated along the choreography. As the choreography does not have a centralized QoS control mechanism, this propagation of tuples can be combined with the algebraic operators to aggregate these increments. For this, we propose to append the API arguments \cite{nikolaos} with \emph{QoS parameters} that may either be self measured by the clients/servers/peers or though a third party aggregation service. 
Note that these rules relate to the \emph{client/peer} side aggregation policies, as we are interested in the effect of choreography participation on client/peer QoS. These are presented in Table \ref{sdkjfghjskahfjkshklkjlshj} and explained further:
\begin{itemize}
	\item \emph{Client-Server} - We begin with a client appending the input QoS increment $q_{req}$ to the interaction. For domains such as $\delta$, this would mean starting a timer $\delta_0$. A synchronous response performs the operation of $\oplus$ on the response QoS increment $q_{res}$. Note that the timeout has been replaced by a generic $\bigvee_q$ increment that may be extended to other domains such as maximum bandwidth reached, for instance. In case of asynchronous response, the supremum $\bigvee$ of the QoS is taken been the response and the proceeded computation from the client $\bigvee q_{req}$. Another metric $q_{\phi}$ represents messages that are passed but may not directly affect QoS perceived by the client.
	\begin{table}[ht]
	\centering
	\begin{tabular}{|p{2.8cm} |p{3cm} | p{6.5cm}|}
	\hline
	\textbf{Interaction}&\textbf{Primitives}&\textbf{Arguments}\\ \hline
	
	Client-Server & \texttt{request} & \texttt{destination, operation, input, $q_{req}$}\\
	&\texttt{sync\_response} & $\uparrow$\texttt{source,} \texttt{operation,} $\uparrow$\texttt{output, $\uparrow q_{req} \oplus q_{res}$, $\bigvee_q$}\\
	&\texttt{async\_response} & $\uparrow$\texttt{source,} \texttt{operation,} $\uparrow$\texttt{output, callback, ~~$\uparrow (\bigvee q_{req}) \oplus q_{res}$}\\
	&\texttt{notify} & \texttt{callback, source, output, $q_{\phi}$}\\
	&\texttt{async\_end\_response} & \texttt{callback, $q_{\phi}$}\\ \hline
	
	
	Publish-Subscribe &	\texttt{publish} & \texttt{broker, filter, event, $\bot_q$, $q_{pub}$ }\\
	&\texttt{subscribe} & \texttt{broker, filter, $\uparrow$handle, $q_{\phi}$}\\
	&\texttt{get\_next} & \texttt{handle, $\uparrow$event, $\bigvee_q$, $\uparrow(\bigvee q_{pub}) \oplus q_{getnext}$}\\
	&\texttt{listen} & \texttt{handle, callback, $q_{\phi}$}\\
  &\texttt{notify} & \texttt{callback, event, $q_{\phi}$}\\
	&\texttt{end\_listen} & \texttt{callback, $q_{\phi}$}\\
	&\texttt{unsubscribe} & \texttt{handle, $q_{\phi}$}\\ \hline
		
	Tuple Space & \texttt{write} & \texttt{tuple\_space, template, tuple, $\bot_q$, $q_{write}$} \\
	&\texttt{take} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, $\bigvee_q$, $\uparrow(\bigvee q_{write}) \oplus q_{read}$}\\
	&\texttt{read} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, $\bigvee_q$, $\uparrow(\bigvee q_{write}) \oplus q_{read}$}\\
	&\texttt{register} & \texttt{tuple\_space, template, callback, $q_{\phi}$}\\
	&\texttt{notify} & \texttt{callback, $q_{\phi}$}\\
  &\texttt{unregister} & \texttt{callback, $q_{\phi}$}\\ \hline	
	%
GA Connector & \texttt{post} & \texttt{coupling\{strong, weak, very weak\}, scope\{(source-destination | broker | tuplespace), (operation | filter | template)\}, data,  $\bot_q$, $q_{post}$}\\
&\texttt{set\_get}& \texttt{coupling, $\uparrow$scope, $\uparrow$handle, $q_{\phi}$}\\
&\texttt{get\_sync}& \texttt{handle, policy, $\uparrow$data, $\bigvee_q$, $\uparrow q_{post} \oplus q_{get}$}\\
&\texttt{get\_async}& \texttt{handle, $\uparrow$data, callback, $\uparrow(\bigvee q_{post}) \oplus q_{get}$}\\
&\texttt{notify} & \texttt{callback, scope, data, $q_{\phi}$}\\
&\texttt{end\_get\_async}&\texttt{callback, $q_{\phi}$}\\
&\texttt{end\_set\_get}&\texttt{handle, $q_{\phi}$} \\\hline
	\end{tabular}
	\caption{QoS increments of interaction paradigms with APIs.}
	\label{sdkjfghjskahfjkshklkjlshj}
	\vspace{-0.35in}
	\end{table}
	
	\item \emph{Publish-Subscribe} - Similarly, we append the publish subscribe interactions with QoS increments. A publisher publishes to a broker with an initial QoS value $q_{pub}$. Subscription to a publishing broker is treated as $q_{\phi}$ which may not directly affect the message reception from the publisher. The \texttt{get\_next} reception appends the value with $(\bigvee q_{pub}) \oplus q_{getnext}$, with $(\bigvee q_{pub})$ representing the supremum of QoS publications (taking care of, for instance, latency appended/data degradation added since publication). Note that the lease period has been replaced with $\bot_q$ and timeout with $\bigvee_q$
	
	
	\item \emph{Tuple Space} - Likewise, tuple spaces are equipped with QoS increments. Note that we treat take and read similarly with both having similar QoS increments. Notification and callbacks are treated with $q_\phi$ as they do not directly affect read/write operations. 
		
	\item \emph{GA Connector} - As the connector abstracts multiple interactions, the post operation is given a generic increment $q_{post}$. To distinguish synchronous and asynchronous get operations, the increments returned are $q_{post} \oplus q_{get}$ and $(\bigvee q_{post}) \oplus q_{get}$, respectively. Operations such as notification and callbacks are, once again, treated as $q_\phi$.
	
\end{itemize}
\noindent Appending the message passing interactions with QoS is shown in Fig. \ref{dfl;jlhgljuioufls}. 

\begin{figure}[ht]
\vspace{-0.1in}
\centering
\includegraphics[height=10cm]{interaction_QoS.eps}
\vspace{-0.1in}
\caption{Message Interaction Paradigms appended with QoS.}
\label{dfl;jlhgljuioufls}
\vspace{-0.2in}
\end{figure}

As the GA connector is able to coordinate with various interaction protocols, a natural extension of our technique is to propagate QoS increments along these connectors. As the connectors have a rich interface, the QoS increments can be suitably transformed into the necessary models for interactions. Such general ``QoS equipped'' message passing would allow choreographies to interact with stateless/stateful services, data feeds and sensors/actuator networks. 
As the GA connector APIs are rich enough, we merely transform the QoS values produced via CS/TS/PS paradigms as values associated with $q_{post}, q_{get}$.  This is realistic as the QoS monitoring from each of the interactions consider the end-to-end response encompassing increments provided by network, middleware and applications. The propagation of these values along the connector is shown in Fig. \ref{akjgfakjhkjashjkh}. Notice that the generic \emph{post} and \emph{get} operations of the GA connectors increment onto the QoS between binding components of CS, TS and PS interactions. We comment on a few salient features of this example:
\begin{itemize}
	\item The CS binding component sends out a request with $q_{req}$ to the GA connector. The response from the PS service comes tagged with $\uparrow q_{post} \oplus  q_{getnext} \oplus (\bigvee q_{pub})$; that from a TS service comes with $\uparrow q_{post} \oplus (\bigvee q_{write}) \oplus q_{read}$. These are provided back to the composite service in the CS paradigm with response linked with $\uparrow q_{req} \oplus (\bigvee q_{res})$. This procedure aggregates the increments produced by both the interactions and the associated connectors.	
	\item The PS binding component sends out a get request with $q_{getnext}$. The response from the CS service comes tagged with $\uparrow q_{post} \oplus  q_{res} \oplus (\bigvee q_{req})$; that from a TS service comes with $\uparrow q_{post} \oplus (\bigvee q_{write}) \oplus q_{read}$. These are provided back to the service in the PS paradigm with response linked with $q_{pub}$, a publication to the broker. 
	\item The TS binding component sends out a get request with $q_{read}$. The response from the CS service comes tagged with $\uparrow q_{post} \oplus  q_{res} \oplus (\bigvee q_{req})$; that from a PS service comes with $\uparrow q_{post} \oplus  q_{getnext} \oplus (\bigvee q_{pub})$. These are provided back to the tuple in the TS paradigm with response linked with $q_{write}$, writing to the tuple space. 
\end{itemize}


\begin{figure}[ht] 
\vspace{-0.1in}
\centering
\includegraphics[height=10cm]{GA_QoS.eps}
\caption{QoS increments propagated with GA Connectors.}
\label{akjgfakjhkjashjkh}
\vspace{-0.2in}
\end{figure}


%\begin{figure}[ht]
%\centering
%\includegraphics[height=14cm]{GA.eps}
%\caption{Message Interaction Paradigms with GA connectors.}
%\label{dsddsgdsxfs}
%\end{figure}



%The QoS enhanaced API is presented below with $|$ representing choice between interaction paradigms. 
%
		%\begin{table}[ht]
	%\centering
	%\begin{tabular}{l | l}
	%\textbf{Primitives}&\textbf{Arguments}\\
	%post & coupling\{strong, weak, very weak\},\\
	%&scope\{source-destination | broker | tuplespace, operation | filter | template\}, data,\\
	%& $\bot_q$, $q_{req} ~|~ q_{pub} ~|~ q_{write}$\\
	%set get& coupling, $\rightarrow$ scope, $\rightarrow$ handle, $q_\phi$\\
	%get syncronous& handle, policy, $\rightarrow$ data, $\bigvee_q$, 
	 %$q_{req} \oplus q_{res}~|~(\bigvee q_{pub}) \oplus q_{get}~|~(\bigvee q_{write}) \oplus q_{read}$\\
	%get asynchronous& handle, $\rightarrow$ data, callback, $(\bigvee q_{req}) \oplus q_{res}~|~(\bigvee q_{pub}) \oplus q_{get}~|~(\bigvee q_{write}) \oplus q_{read}$\\
	%notify & callback, scope, data, $q_\phi$\\
	%end get asynchronous&callback, $q_\phi$\\
	%end set get&handle, $q_\phi$
	%\end{tabular}
	%\caption{Tuple Space API.}
	%\end{table}

\section{Results: QoS in Choreography Interactions}
\label{sdkgjlksdjgklsjglsjd}
As we have described earlier, choreographies can involve heterogeneous interactions between both services, things(sensors/actuators), computational entities and human participants. The use of our QoS analysis enables the following:

\begin{enumerate}
	\item In depth study of interaction paradigms and the effect on end-to-end QoS. The composition models in these cases would have to take into account the nature of the interaction and their effect on the composed QoS. This would primarily be done at \emph{design-time} with previously collected statistics.
	\item In many cases, similar functionality may be replicated by services/things in a registry. Using a particular domain (say timeliness $\delta$) as the focus of the QoS, we study at \emph{runtime}, the possibility of choosing a particular binding to prevent deterioration of output QoS. 
\end{enumerate}

\subsection{Comparison of Tradeoffs}

To compare effect of CS/PS/TS paradigms on QoS metrics such as timeliness, security and message efficiency, simulations were performed. We assume for uniform comparison between interactions that the QoS increments $q_{req}$, $q_{post}$, $q_{pub}$ and so on are random numbers drawn from distributions with similar mean and variances. The QoS metric values were distributions with $\delta$ drawn from a \emph{heavy-tailed} distribution; $\mathcal{S}$ from a \emph{uniform} distribution; $\lambda$ from an \emph{exponential} distribution. The details for the specific interactions:
\begin{itemize}
	\item \emph{Client Server} - At $(\delta_0, \mathcal{S}_0, \lambda_0)$, every client sends a request to a single server. The response is linked with the end-to-end latency, security level and the message efficiency (number of messages passed per request). The mean values for $N$ clients are displayed as the output QoS.
	\item \emph{Publish Subscribe} - At $(\delta_0, \mathcal{S}_0, \lambda_0)$, a publisher sends data to a broker, which is then forwarded to $N$ peers. We assume that the subscription messages are already received by the broker and the messages can be procured (getnext) immediately by the peers. The subscription level messages, are however, considered during message efficiency calculations.	
	\item Tuple Space - At $(\delta_0, \mathcal{S}_0, \lambda_0)$, data is written to a tuple which may be read by $N$ clients. Note that there may be QoS increments introduced between writing, pattern-matching and reading from the tuple.
\end{itemize}

As shown in Fig. \ref{xzvsdgsdtwe}, there are differences in performance of these schemes for the evaluated QoS metrics. In case of \emph{Timeliness} $\delta$, PS and CS schemes are shown to outperform the TS scheme when the mean end-to-end latencies are considered for clients/peers. For \emph{Security} $\mathcal{S}$, as an intermediate tuple or broker are employed by the PS/TS schemes, the security levels are consistently lower than that of the CS scheme. \emph{Message Efficiency} $\lambda$ considers individual subscriptions needed by the PS scheme, which increases the number of messages per interaction.
\begin{figure}[ht]
\vspace{-0.3in}
\centering
\includegraphics[width=\columnwidth]{5users.eps}
\caption{QoS composition with CS, TS, PS paradigms.}
\label{xzvsdgsdtwe}
\vspace{-0.25in}
\end{figure}

Also shown in Fig. \ref{xzvsdgsdvxfgfvdwe} is the effect of using GA connectors on these metrics. An improvement $\delta$ performance by CS-PS connectors is traded off with deteriorating $\lambda$. Thus, if cost of bandwidth is to be taken into consideration, a choice can be made at design time to select a particular connector over another. This would mean discovering services that are implemented with such interaction paradigms. In case this is not exposed, the worst case performance for each domains must be expected at design time. At runtime, if re-configuration \cite{reconfig_chor} or replacement/late-binding occurs \cite{Optimization4}, changes that may be expected through varied interaction paradigms may be evaluated. For instance, reduced $\mathcal{S}$ may be traded off with improvements in $\delta$. 
\begin{figure}[ht]
\vspace{-0.15in}
\centering
\includegraphics[width=\columnwidth]{5usersCSTS.eps}
\caption{QoS composition with GA connectors.}
\label{xzvsdgsdvxfgfvdwe}
\vspace{-0.25in}
\end{figure}

\subsection{Substituting Interactions}
In large spaces of services and devices \cite{iot1}, replacement and late-binding procedures are commonly employed. The replacement of heterogeneous devices in such cases should take into account the interaction paradigms and their corresponding QoS. A level of control is to check if the is replacement would not affect the particular QoS metric in hand. In order to compare the statistics provided by two interaction paradigms, we employ nonparametric hypothesis tests.

The two-sample \emph{Kolmogorov-Smirnov} test \cite{KS_test} is a nonparametric hypothesis test that evaluates the difference between the cumulative distribution functions of two sample data. This test may also be used to test whether two underlying one-dimensional probability distributions differ. In this case, the Kolmogorov-Smirnov statistic is:
\begin{equation}
\mathbf{KS}_{n,n'}=\sup_{q} |F_{1,n}({q})-F_{2,n'}({q})|
\end{equation}
where $F_{1,n}$ and $F_{2,n'}$ are the empirical distribution functions of the first and the second sample respectively. The hypothesis test result is returned as a logical value:
\begin{itemize}
\item If $\mathbf{h} = 0$, this indicates an acceptance of the null hypothesis at $\alpha$ significance level: that the data in vectors ${q}_1$ and ${q}_2$ are from the same continuous distribution.
	\item If $\mathbf{h} = 1$, this indicates the rejection of the null hypothesis at $\alpha$ significance level: the alternative hypothesis is that ${q}_1$ and ${q}_2$ are from different continuous distributions. 
\end{itemize}
The null hypothesis is rejected at level $\alpha$ if:
\begin{equation}
\sqrt{\frac{n n'}{n + n'}}\mathbf{KS}_{n,n'}>K_\alpha
\end{equation}
We make use of this test on the observations of the CS, TS, PS schemes when applied to connectors, such as in Fig. \ref{xzvsdgsdvxfgfvdwe}. This is to determine whether the performance of a particular scheme can be safely replaced with another connector when querying for a particular metric ($\delta, \mathcal{S}, \lambda$). We set this tests in MATLAB with $\alpha = 1\%$ as \texttt{[H,P,KSSTAT] = kstest2(q1,q2,0.01,'unequal')}. The outputs are given in Table \ref{dkjsghskjdjghkjswhbdfj}.

\begin{table}[ht]
\vspace{-0.1in}
\centering
\begin{tabular}{c|c|c|c}
\multicolumn{4}{c}{$\delta$: \textbf{Timeliness}~ (20 peers)} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 1;~KSstat = 0.3143}&\texttt{h = 0;~KSstat = 0.0134}\\
CS-TS&\texttt{h = 1;~KSstat = 0.3143}&--&\texttt{h = 1;~KSstat = 0.3064}\\
PS-TS&\texttt{h = 0;~KSstat = 0.0134}&\texttt{h = 1;~KSstat = 0.3064}&--\vspace{0.1in}\\

\multicolumn{4}{c}{$\mathcal{S}$: \textbf{Security}~ (20 peers)} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 0;~KSstat = 0.0079}&\texttt{h = 1;~KSstat = 0.1451}\\
CS-TS&\texttt{h = 0;~KSstat = 0.0079}&--&\texttt{h = 1;~KSstat = 0.1506}\\
PS-TS&\texttt{h = 1;~KSstat = 0.1451}&\texttt{h = 1;~KSstat = 0.1506}&--\vspace{0.1in}\\

\multicolumn{4}{c}{$\lambda$: \textbf{Message Efficiency}~ (20 peers)} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 1;~KSstat = 0.5031}&\texttt{h = 0;~KSstat = 0.0071}\\
CS-TS&\texttt{h = 1;~KSstat = 0.5031}&--&\texttt{h = 1;~KSstat = 0.4990}\\
PS-TS&\texttt{h = 0;~KSstat = 0.0071}&\texttt{h = 1;~KSstat = 0.4990}&--\vspace{0.1in}\\
\end{tabular}
\caption{KS Tests applied to various connectors.}
\label{dkjsghskjdjghkjswhbdfj}
\vspace{-0.3in}
\end{table}

This provides some interesting results: assuming certain distributions on the underlying services (as in Fig. \ref{xzvsdgsdvxfgfvdwe}), for timeliness $\delta$, the CS-PS interaction can be suitably replaced by the PS-TS interaction; for security $\mathcal{S}$, the CS-PS interaction can be suitably replaced by the CS-TS interaction; for message efficiency $\lambda$, the CS-PS interaction can be suitably replaced by the PS-TS interaction. Though this can change according to measurements and collected statistics, this procedure can be applied in general cases to safely replace interactions. For example, if contractual obligations and SLAs need to be met in certain domains, deterioration of the QoS metrics due to replacement would be deterred. This sort of comparison not only takes into account the probabilistic nature of the QoS metrics, but also the tradeoffs provided due to the multi-dimensional QoS evaluation and corresponding interaction paradigms.

\section{Related Work}
\label{fsdmlkjflksdjk}
We review some of the literature available on QoS compositions in web services choreographies, heterogeneous interactions and QoS aware middleware.

QoS issues in web services span multiple topics such as optimal late-binding (discovery, selection, substitution) and contract management (SLAs, negotiation, monitoring). In \cite{Jaeger2004}, Jaeger et al. provide a comprehensive analysis of QoS composition with associated workflow patterns. Such aggregation techniques are used by Zeng et al. \cite{QoS_composition} for optimal decomposition of global QoS constraints into local constraints. In \cite{Optimization4}, the optimization of dynamic service compositions are modeled as a multidimension-multichoice knapsack problem (MMKP). 

While QoS issues in composite services based on centralized control (orchestrations) has received some attention \cite{osullivan}, the metrics relevant to choreographies are an active area of research. In \cite{QoS_choreography}, Mancioppi et al. provide a structured overview of the possible metrics to be incorporated. Xiangpeng et al. \cite{QoS_choreography2} provide a formal analysis of integrating QoS into the language \emph{Chor} and provide composition techniques for latency and cost. Automatic triggers and strategies for QoS aware re-planning of composite orchestrations are studied in \cite{QoS_composition6}, which may prove promising for extension into choreographies. In our paper, we provide an algebraic formulation based on multi-dimensional probabilistic QoS models \cite{sidney6} that may be composed in the case of choreographies.

With an increasing number of devices being interconnected through the Internet of Things \cite{iot1}, extensions to the SOA based ESB middleware adapter \cite{esb} are required. In the \choreos project \cite{choreos}, the generic application protocol is provided as an alternative to this which incorporates multiple interaction paradigms. This can connect REST \cite{restful}, Java Messaging Service \cite{JMS} and Javaspaces \cite{javaspaces}. Middleware for messaging based services has been studied in \cite{mom} with emphasis on the space-time coupling involved.  

In \cite{qos_middleware}, QoS is integrated in middleware architecture for discovery, configuration and deployment analysis. In \cite{pubsub_QoS}, the characteristics of publish-subscribe interactions that are crucial to QoS composition are studied in considerable detail.  in \cite{mom_QoS}, the publish-subscribe middleware interaction is upgraded with the \emph{Harmony} overlay messaging to prevent runtime QoS deterioration.

Our work builds on heterogeneous interaction paradigms and enhances them with QoS composition rules. While QoS in the typical web services setting is done at the application level, capturing the fine-grained interactions within heterogeneous paradigms provide us with a detailed outlook of QoS aggregation policies. These may be exploited during design-time selection or runtime replacement as demonstrated in our work.

\section{Conclusions}
\label{dfjsudhfiuwshhio}
QoS analysis in choreographies typically consider homogeneous client-server interactions and are performed at the application level. Choreographies of heterogeneous devices such as those in the Internet of Things require further fine-grained QoS analysis of underlying interaction paradigms. In this paper, we study the effect of heterogeneous middleware connectors, such as the GA-connectors from the \choreos project, on choreography QoS metrics. Using multi-dimensional, probabilistic QoS metrics and an algebraic model for QoS aggregation, this procedure reveals some interesting results. The tradeoffs in particular QoS domains may be studied along with interactions for efficient selection during design-time. Through statistical tests such as Kolmogorov-Smirnov, runtime replacement of a particular interaction with another can also be performed. This provides a useful toolkit for QoS analysis in heterogeneous choreography environments.

\bibliographystyle{splncs}
\bibliography{icsoc}


%\begin{thebibliography}{4}
%
%\bibitem{jour} Smith, T.F., Waterman, M.S.: Identification of Common Molecular
%Subsequences. J. Mol. Biol. 147, 195--197 (1981)
%
%\bibitem{lncschap} May, P., Ehrlich, H.C., Steinke, T.: ZIB Structure Prediction Pipeline:
%Composing a Complex Biological Workflow through Web Services. In: Nagel,
%W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol. 4128,
%pp. 1148--1158. Springer, Heidelberg (2006)
%
%\bibitem{book} Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing
%Infrastructure. Morgan Kaufmann, San Francisco (1999)
%
%\bibitem{proceeding1} Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C.: Grid
%Information Services for Distributed Resource Sharing. In: 10th IEEE
%International Symposium on High Performance Distributed Computing, pp.
%181--184. IEEE Press, New York (2001)
%
%\bibitem{proceeding2} Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the
%Grid: an Open Grid Services Architecture for Distributed Systems
%Integration. Technical report, Global Grid Forum (2002)
%
%\bibitem{url} National Center for Biotechnology Information, \url{http://www.ncbi.nlm.nih.gov}
%
%\end{thebibliography}


\end{document}
